樹（Tree）是一種非線性的階層資料結構，模擬現實世界中的組織架構（例如檔案系統或家譜）。與清單、堆疊和佇列的線性排列不同，樹的本質在於其階層性（Hierarchical）與遞歸性（Recursive）。
1. 解剖樹的形態
- 節點（Node）：包含鍵（Key）和有效載荷的基本單元。
- 根節點（Root）：唯一沒有入邊的節點，是樹的起點。
- 邊（Edge）：連接節點的唯一路徑，代表父子關係。
- 葉節點（Leaf）: 没有子节点的末端，是递归终止的自然边界。
2. 遞歸定義的雙重視角
我們可以從兩種視角來理解樹：
圖形學視角
由節點與邊構成的無環、連通圖，每個節點（除根節點外）有且僅有一個父節點。
由節點與邊構成的無環、連通圖，每個節點（除根節點外）有且僅有一個父節點。
遞歸視角
一棵樹要麼為空，要麼由一個根節點及零個或多個子樹（Subtree）組成。
一棵樹要麼為空，要麼由一個根節點及零個或多個子樹（Subtree）組成。
HTML DOM 樹範例
在 HTML 中，
<html> 是根，<body> 和 <head> 是兄弟節點。每一個標籤及其巢狀內容共同構成一棵子樹。這種結構使我們能整體移動 <ul> 及其所有 <li> 而不破壞其內部階層。